package 复习.面试TOP101.二分查找和排序;

public class 数组中的逆序对 {
    int count = 0;
    public int InversePairs(int [] array) {
        if(array.length < 2) return -1;
        merge(array,0,array.length - 1);
        return count;
    }

    public void merge(int[] arr,int left,int right){
        int mid = left + (right - left) >> 1;
        if(left < right){
            merge(arr,left,mid);
            merge(arr,mid + 1,right);
            mergeSort(arr,left,mid,right);
        }
    }

    public void mergeSort(int[] arr,int left,int mid,int right){
        int[] tmp = new int[right - left + 1];
        int tmpIndex = 0;//记录临时数组下标
        int leftIndex = left;
        int rightIndex = mid + 1;
        while(leftIndex <= mid && rightIndex <= right){
            if(arr[leftIndex] <= arr[rightIndex]){
                tmp[tmpIndex++] = arr[leftIndex++];
            }else{
                tmp[tmpIndex++] = arr[rightIndex++];
                count += mid - leftIndex + 1;
                count %= 1000000007;
            }
        }
        while(leftIndex <= mid){
            tmp[tmpIndex++] = arr[leftIndex++];
        }
        while (rightIndex <= right){
            tmp[tmpIndex++] = arr[rightIndex++];
        }
        for(int i:tmp){
            arr[left++] = i;
        }
    }
}
/*
public class Solution {
    int count = 0;
    public int InversePairs(int [] array) {
        if(array.length < 2) return -1;
        merge(array,0,array.length - 1);
        return count;
    }

    public void merge(int[] arr,int left,int right){
        int mid = (right + left) / 2;
        if(left < right){
            merge(arr,left,mid);
            merge(arr,mid + 1,right);
            mergeSort(arr,left,mid,right);
        }
    }

    public void mergeSort(int[] arr,int left,int mid,int right){
        int[] array = new int[right - left + 1];
        int leftIndex = left;//左数组起始下标
        int rightIndex = mid + 1;//右数组起始下标
        int index = left;//原数组其实下标
        int arrayIndex = 0;//临时数组下标起始点
        while(leftIndex <= mid &&  rightIndex <= right){
            if(arr[leftIndex] <= arr[rightIndex]){
                array[arrayIndex] = arr[leftIndex];
                leftIndex++;
                arrayIndex++;
            }else{
                array[arrayIndex] = arr[rightIndex];
                rightIndex++;
                arrayIndex++;
                count += mid - leftIndex + 1;
                count %= 1000000007;
            }
        }
        while(leftIndex <= mid)
            array[arrayIndex++] = arr[leftIndex++];
        while(rightIndex <= right)
            array[arrayIndex++] = arr[rightIndex++];
        for(int i:array){
            arr[index++] = i;
        }
    }
}

 */